# Python 2.6.4
# Project Euler, Problem 113all
# Copyright 2010 Talha Zaman

def bouncy(n):
    prev = int(str(n)[0])
    up, down = False, False
    for i in [int(x) for x in str(n)[1:]]:
        if i > prev: up = True
        elif i < prev: down = True
        prev = i
    return up and down

def upper(n):
    prev = int(str(n)[0])
    up, down = False, False
    for i in [int(x) for x in str(n)[1:]]:
        if i > prev: up = True
        elif i < prev: down = True
        prev = i
    return not down

def downer(n):
    prev = int(str(n)[0])
    up, down = False, False
    for i in [int(x) for x in str(n)[1:]]:
        if i > prev: up = True
        elif i < prev: down = True
        prev = i
    return not up

def downers(digit):
    tot = 1
    for i in range(1, digit+1):
        tot += uppers(i, 0) - 1
    return tot
    
def uppers(digit, prevnum):
    if (digit==1): return 10-prevnum
    tot = 0
    for i in range(prevnum, 10):
        tot += uppers(digit-1, i)
    return tot

def nonbouncy(digit):
    base = range(11)
    next = [0]*11
    down = 0
    for digits in range(digit-1):
        down += base[10] - 1
        for i in range(11):
            next[i] = sum([base[j] for j in range(i+1)])
        base, next = next, [0]*11
    return base[10]+base[10]+down-bothcount(digit)-1

def bothcount(digit):
    return 9*(digit-1)+10

def counts(n):
    up, down, both, bons = 0, 0, 0, 0
    for i in range(n):
        up += upper(i)
        down += downer(i)
        bons += bouncy(i)
        both += upper(i) and downer(i)
    print "Up:", up, "Down:", down, "Both:", both, "Bouncy:", bons

